package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 将字符串拆分为递减的连续值
 */

public class Code1849 {
    public static void main(String[] args) {
        String s = "99999999999999999998";
        System.out.println(new Code1849().splitString(s));
    }

    public boolean splitString(String s) {
        long t = 0;     //枚举第一个数字的值，因为s长度为20，所以会超过int，要用long类型
        for (int i = 0; i < s.length() - 1; i++) {  //因为必须要分割成两个子串，所以最后一个字符不可能是组成第一个数字的字符，我们这里也是为了防止刚好20位导致long也会溢出的情况
            t = t * 10 + s.charAt(i) - '0'; //把当前字符加入到组成第一个数字的字符集中
            if (t > 10000000000L)    //如果t大于10^10那么后面最多还有9位数，所以不可能组成递减的连续值
                return false;
            if (dfs(s, t, i + 1))   //把t当作第一个数字，找寻后面递减的数
                return true;
        }
        return false;
    }

    //s要分割的字符串；pre前面一个数的值；k当前字符串已经用到了哪个位置
    private boolean dfs(String s, long pre, int k) {
        if (k == s.length())    //代表能组成递减的连续值
            return true;
        long t = 0;     //枚举pre后面的一个数字的值
        for (int i = k; i < s.length(); i++) {  //从第k个字符开始组成数字
            t = t * 10 + s.charAt(i) - '0';
            if (t > 10000000000L)
                return false;
            if (pre - 1 == t && dfs(s, t, i + 1))   //如果前面一个数字和当前数组相差为1，则继续往下面寻找满足条件的数组
                return true;
            if (t >= pre)   //当前组成的数大于前面的数表示不符合要求，直接返回false
                return false;
        }
        return false;
    }

    public boolean splitString1(String s) {

        return backtrace(s, 0, new ArrayList<>());
    }

    private boolean backtrace(String s, int index, List<Long> list) {
        if (index == s.length()) {
            return list.size() > 1;
        }

        for (int end = index + 1; end <= s.length(); end++) {
            long cur = Long.parseLong(s.substring(index, end));
            if (cur > 10000000000L)
                break;
            if (list.isEmpty()) {
                list.add(cur);
                boolean flag = backtrace(s, end, list);
                if (flag) return true;
                list.remove(list.size() - 1);
                continue;
            }
            if (cur - list.get(list.size() - 1) != -1)
                continue;
            list.add(cur);
            boolean flag = backtrace(s, end, list);
            if (flag) return true;
            list.remove(list.size() - 1);
        }
        return false;
    }
}
